(0) Obligation:
The Runtime Complexity (innermost) of the given
CpxTRS could be proven to be
BOUNDS(1, n^1).
The TRS R consists of the following rules:
max(L(x)) → x
max(N(L(0), L(y))) → y
max(N(L(s(x)), L(s(y)))) → s(max(N(L(x), L(y))))
max(N(L(x), N(y, z))) → max(N(L(x), L(max(N(y, z)))))
Rewrite Strategy: INNERMOST
(1) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 1.
The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by:
final states : [1]
transitions:
L0(0) → 0
N0(0, 0) → 0
00() → 0
s0(0) → 0
max0(0) → 1
L1(0) → 4
L1(0) → 5
N1(4, 5) → 3
max1(3) → 2
s1(2) → 1
N1(0, 0) → 8
max1(8) → 7
L1(7) → 6
N1(4, 6) → 3
max1(3) → 1
s1(2) → 7
max1(3) → 7
L1(2) → 5
0 → 1
0 → 7
0 → 2
7 → 1
7 → 2
2 → 1
2 → 7
(2) BOUNDS(1, n^1)